package com.rising.face.ali.bishi.stack;

import java.util.Stack;

/**
 * @Author: rising
 * @Description:
 * 设计一个栈，这个栈除了支持普通的push, pop操作之外，还提供一个函数min(), 以返回栈中元素的最小值，要求min()的时间复杂性为O(1).
 * 提示：可以用现有的任何数据结构，如队列、队、另外的栈，等等。 优化：要求实现push(), pop()的时间复杂性也为O(1)
 * @Date: create in 2021/2/28 15:02
 */
public class MinStack {

    private Stack<Integer> dataStack;
    private Stack<Integer> minStack;

    public MinStack() {
        this.dataStack = new Stack<Integer>();
        this.minStack = new Stack<Integer>();
    }

    //压栈，如果最小栈为空，或者比最小数据还小，则往最小栈里面压一份，
    public void push(int x) {
        if (this.minStack.isEmpty()) {
            this.minStack.push(x);
        } else if(x <= this.min()) {
            this.minStack.push(x);
        }
        this.dataStack.push(x);
    }

    //pop()函数返回栈顶的元素，并且将该栈顶元素出栈。
    //需要同时检查最小栈栈顶数据是不是和数据栈的栈顶元素一致。
    public int pop() {
        if (this.dataStack.isEmpty()) {
            throw new RuntimeException("stack is Empty");
        }
        int result = this.dataStack.pop();
        if (result == this.min()) {
            this.minStack.pop();
        }
        return result;
    }

    //获取栈顶元素，但是不出栈
    public int top() {
        if(this.dataStack.isEmpty()) {
            throw new RuntimeException("stack is Empty");
        }
        return this.dataStack.peek();
    }

    //获取最小元素
    public int min() {
        if(this.minStack.isEmpty()) {
            throw new RuntimeException("stack is Empty");
        }
        return this.minStack.peek();
    }

    public static void main(String[] args) {
        MinStack minStack = new MinStack();
        minStack.push(10);
        minStack.push(11);
        minStack.push(134);
        minStack.push(10);
        minStack.push(1);
        minStack.push(189);
        minStack.push(456);

        System.out.println("栈顶元素：" + minStack.top());
        System.out.println("最小元素：" + minStack.min());
        System.out.println("----------------------------");
        System.out.println("出栈：" + minStack.pop());
        System.out.println("栈顶元素：" + minStack.top());
        System.out.println("最小元素：" + minStack.min());
        System.out.println("----------------------------");
        System.out.println("出栈：" + minStack.pop());
        System.out.println("栈顶元素：" + minStack.top());
        System.out.println("最小元素：" + minStack.min());
        System.out.println("----------------------------");
        System.out.println("出栈：" + minStack.pop());
        System.out.println("栈顶元素：" + minStack.top());
        System.out.println("最小元素：" + minStack.min());
        System.out.println("----------------------------");
        System.out.println("出栈：" + minStack.pop());
        System.out.println("栈顶元素：" + minStack.top());
        System.out.println("最小元素：" + minStack.min());
        System.out.println("----------------------------");
        System.out.println("出栈：" + minStack.pop());
        System.out.println("栈顶元素：" + minStack.top());
        System.out.println("最小元素：" + minStack.min());
        System.out.println("----------------------------");
        System.out.println("出栈：" + minStack.pop());
        System.out.println("栈顶元素：" + minStack.top());
        System.out.println("最小元素：" + minStack.min());
    }
}
